//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//
//
//
// 注意：
//
//
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。
//
//
//
//
// 示例 1：
//
//
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//
//
// 示例 2：
//
//
//输入：s = "a", t = "a"
//输出："a"
//
//
// 示例 3:
//
//
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。
//
//
//
// 提示：
//
//
// 1 <= s.length, t.length <= 10⁵
// s 和 t 由英文字母组成
//
//
//
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 👍 1607 👎 0

package leetcode.editor.cn;

import java.util.HashMap;

@SuppressWarnings("all")
//Java：最小覆盖子串
public class 最小覆盖子串 {
    public static void main(String[] args) {
        Solution solution = new 最小覆盖子串().new Solution();
        // TO TEST
        String window = solution.minWindow("ADOBECODEBANC", "BANC");

        System.out.println(window);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {

            if (t.length() > s.length())
                return "";
            HashMap<Character, Integer> counts = new HashMap<>();
            for (int i = 0; i < t.length(); i++) {
                char key = t.charAt(i);
                counts.put(key, counts.getOrDefault(key, 0) + 1);
            }
            int left = 0, right = 0;
            int i = 0, j = 0;//
            int min = Integer.MAX_VALUE;
            while (right < s.length()) {
                char charAtRight = s.charAt(right);
                if (counts.containsKey(charAtRight)) {
                    counts.put(charAtRight, counts.get(charAtRight) - 1);
                }

                while (check(counts)) {
                    int current = right - left + 1;
                    if (current < min) {
                        min = current;
                        i = left;
                        j = right;
                    }
                    char charAtLeft = s.charAt(left);
                    if (counts.containsKey(charAtLeft)) {
                        counts.put(charAtLeft, counts.get(charAtLeft) + 1);
                    }
                    left++;
                }

                right++;

            }


            if (min == Integer.MAX_VALUE)
                return "";
            return s.substring(i, j + 1);
        }

        private boolean check(HashMap<Character, Integer> counts) {
            for (Integer value : counts.values()) {
                if (value > 0)
                    return false;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
